class Node:
    
    # parent: Integer , index of your parent node
    # cost: the cost of reaching this node from the root.
    # depth: the depth of the node in the search tree (from the root)
    # operator: a tuple(operator, block, distance)
    # state: a string representing a 6 x 6 grid
    def __init__(self, p, c, o, s, heuristic=0):
        self.parent = p
        if p:
            # if the node has a parent (ie, it is not the root node),
            # then assign the cost and depth relative to the parent
            self.cost = p.cost + c
            self.depth = p.depth + 1
        else:
            self.cost = c
            self.depth = 0
        self.operator = o
        self.state = s
        self.heuristic = heuristic
    def __str__(self):
        return '\n'.join(MouseInMaze.get_grid(self.state))


# A search problem consists of the initial state which may be represented as
# a Node structure, a set of operators that can be applied to the search problem
# to change its current state and a goal test function that can be applied to a state representation.
class SearchProblem:
    
    # operators: a list of functions
    # initial_state: a string representing a 6 x 6 grid
    # goal_test: a function checking whether the mouse can be out
    def __init__(self, ops, init_st, gt):
        self.operators = ops
        self.operator_names = [e.__name__ for e in self.operators]
        self.initial_state = init_st
        self.goal_test = gt
        
    def expand(self, node):
        # apply all operators on node and return list of next nodes
        next_nodes = []
        for op in self.operators:
            next_nodes.extend(op(node))
        return next_nodes
        

class MouseInMaze(SearchProblem):
    height = 6
    width = 6
    
    def __init__(self, initial_state):
        SearchProblem.__init__(self, 
        [MouseInMaze.move_up, MouseInMaze.move_down, MouseInMaze.move_right, MouseInMaze.move_left],
        initial_state, MouseInMaze.mim_goal_test)
        
    # return a list of strings representation given the flat string representation of 36 characters
    def get_grid(confstr):
        return [confstr[i * MouseInMaze.width: (i + 1) * MouseInMaze.width] for i in range(MouseInMaze.height)]
    
    # The functions move_up, .. etc, given a node, return a list of nodes which represent
    # the states resulting from the corresponding move applied in all possible ways on all
    # possible blocks in the state represented by the given node
    def move_up(node):
        grid = MouseInMaze.get_grid(node.state)
        res_nodes = []
        for i in range(1, MouseInMaze.height):
            for j in range(MouseInMaze.width):
                # check the existence of a block in location (i,j)
                if grid[i][j] >= 'a' and grid[i][j] <= 'z':
                    # check whether the block was handled before
                    if grid[i - 1][j] == grid[i][j]:
                        continue
                    # check orientation of block (horizontal vs vertical). move_up is possible for vertical blocks only
                    if j > 0 and grid[i][j - 1] == grid[i][j] or j < MouseInMaze.width - 1 and grid[i][j + 1] == grid[i][j]:
                        continue
                    # determine the size of the block (2 or 3 units)
                    if i + 2 >= MouseInMaze.height or grid[i + 2][j] != grid[i][j]:
                        lower = i + 1
                    else:
                        lower = i + 2
                    length = lower - i + 1
                    upper = i - 1
                    # loop on all possible destinations to which the block may be moved
                    while upper >= 0:
                        if grid[upper][j] != '.':
                            # break if there is no more space to simulate further possible moves for the block occupying location (i,j)
                            break
                        # simulate the move by modifying the board configuration in a new string
                        confstr_list = []
                        for s in grid:
                            confstr_list.extend(list(s))
                        confstr_list[upper * MouseInMaze.width + j] = grid[i][j]
                        confstr_list[(upper + 1) * MouseInMaze.width + j] = grid[i][j]
                        if length == 3:
                            confstr_list[(upper + 2) * MouseInMaze.width + j] = grid[i][j]
                        for empty_i in range(upper + length, lower + 1):
                            confstr_list[empty_i * MouseInMaze.width + j] = '.'
                        # create a node for the state representing the simulated move
                        res_nodes.append(Node(node, 1, (MouseInMaze.move_up, grid[i][j], i - upper), ''.join(confstr_list))) # node.cost +1  not 1 (can be in constructor)
                        upper -= 1
        return res_nodes
        
    def move_down(node):
        grid = MouseInMaze.get_grid(node.state)
        res_nodes = []
        for i in reversed(range(MouseInMaze.height - 1)):
            for j in range(MouseInMaze.width):
                if grid[i][j] >= 'a' and grid[i][j] <= 'z':
                    if grid[i + 1][j] == grid[i][j]:
                        continue
                    if j > 0 and grid[i][j - 1] == grid[i][j] or j < MouseInMaze.width - 1 and grid[i][j + 1] == grid[i][j]:
                        continue
                    if i - 2 < 0 or grid[i - 2][j] != grid[i][j]:
                        upper = i - 1
                    else:
                        upper = i - 2
                    length = i - upper + 1
                    lower = i + 1
                    while lower < MouseInMaze.height:
                        if grid[lower][j] != '.':
                            break
                        confstr_list = []
                        for s in grid:
                            confstr_list.extend(list(s))
                        confstr_list[lower * MouseInMaze.width + j] = grid[i][j]
                        confstr_list[(lower - 1) * MouseInMaze.width + j] = grid[i][j]
                        if length == 3:
                            confstr_list[(lower - 2) * MouseInMaze.width + j] = grid[i][j]
                        for empty_i in range(upper, lower - length + 1):
                            confstr_list[empty_i * MouseInMaze.width + j] = '.'
                        res_nodes.append(Node(node, 1, (MouseInMaze.move_down, grid[i][j], lower - i), ''.join(confstr_list)))
                        lower += 1
        return res_nodes
        
    def move_right(node):
        grid = MouseInMaze.get_grid(node.state)
        res_nodes = []
        for j in reversed(range(MouseInMaze.width - 1)):
            for i in range(MouseInMaze.height):
                if grid[i][j] >= 'a' and grid[i][j] <= 'z' or grid[i][j] == '*':
                    if grid[i][j + 1] == grid[i][j]:
                        continue
                    if i > 0 and grid[i - 1][j] == grid[i][j] or i < MouseInMaze.height - 1 and grid[i + 1][j] == grid[i][j]:
                        continue
                    if j - 2 < 0 or grid[i][j - 2] != grid[i][j]:
                        left_most = j - 1
                    else:
                        left_most = j - 2
                    length = j - left_most + 1
                    right_most = j + 1
                    while right_most < MouseInMaze.width:
                        if grid[i][right_most] != '.':
                            break
                        confstr_list = []
                        for s in grid:
                            confstr_list.extend(list(s))
                        confstr_list[i * MouseInMaze.width + right_most] = grid[i][j]
                        confstr_list[i * MouseInMaze.width + right_most - 1] = grid[i][j]
                        if length == 3:
                            confstr_list[i * MouseInMaze.width + right_most - 2] = grid[i][j]
                        for empty_j in range(left_most, right_most - length + 1):
                            confstr_list[i * MouseInMaze.width + empty_j] = '.'
                        res_nodes.append(Node(node, 1, (MouseInMaze.move_right, grid[i][j], right_most - j), ''.join(confstr_list)))
                        right_most += 1
        return res_nodes
        
    def move_left(node):
        grid = MouseInMaze.get_grid(node.state)
        res_nodes = []
        for j in range(1, MouseInMaze.width):
            for i in range(MouseInMaze.height):
                if grid[i][j] >= 'a' and grid[i][j] <= 'z' or grid[i][j] == '*':
                    if grid[i][j - 1] == grid[i][j]:
                        continue
                    if i > 0 and grid[i - 1][j] == grid[i][j] or i < MouseInMaze.height - 1 and grid[i + 1][j] == grid[i][j]:
                        continue
                    if j + 2 >= MouseInMaze.width or grid[i][j + 2] != grid[i][j]:
                        right_most = j + 1
                    else:
                        right_most = j + 2
                    length = right_most - j + 1
                    left_most = j - 1
                    while left_most >= 0:
                        if grid[i][left_most] != '.':
                            break
                        confstr_list = []
                        for s in grid:
                            confstr_list.extend(list(s))
                        confstr_list[i * MouseInMaze.width + left_most] = grid[i][j]
                        confstr_list[i * MouseInMaze.width + left_most + 1] = grid[i][j]
                        if length == 3:
                            confstr_list[i * MouseInMaze.width + left_most + 2] = grid[i][j]
                        for empty_j in range(left_most + length, right_most + 1):
                            confstr_list[i * MouseInMaze.width + empty_j] = '.'
                        res_nodes.append(Node(node, 1, (MouseInMaze.move_left, grid[i][j], j - left_most), ''.join(confstr_list)))
                        left_most -= 1
        return res_nodes
    
    # check that the mouse is free to move out of the maze by just moving it right.
    def mim_goal_test(confstr):
        mouse_location = confstr.find('*')
        i = mouse_location
        mouse_free = True
        while i <= 2 * 6 + 5:
            mouse_free &= (confstr[i] == '.' or confstr[i] == '*')
            i += 1
        return mouse_free
    
    
class SearchAlgorithm:
    CUT_OFF = -1
    FAILURE = None
    visited = None
    
    # returns a key on the node for sorting the nodes for a greedy search
    def compare_greedy(node):
        return node.heuristic
    
    # returns a key on the node for sorting the nodes for an A* search
    def compare_a(node):
        return node.cost + node.heuristic
        
    def make_node(state):
        return Node(None, 0, 'no_op', state)
    
    def make_queue(node):
        return [node];
    
    # print step-by-step instructions for the moves that have lead to the solution
    # represented by the state of the given node. This function also prints the board
    # configuration sequence after each move starting from the initial state until
    # reaching the given solution
    def print_solution(node):
        l = []
        while node:
            l = [node] + l
            node = node.parent
        for node in l:
            if node.operator != 'no_op':
                print(node.operator[0].__name__ + ' block ' + node.operator[1]
                + ' for ' + str(node.operator[2]) + ' steps')
            print (node)

    def get_moves(node):
        l = []
        while node:
            l = [node.operator] + l
            node = node.parent
        return l
        
    def BFS(fringe, nodes):
        fringe.extend(nodes)
        return fringe
    
    def DFS(fringe, nodes):
        fringe = nodes + fringe
        return fringe
        
    # Assign to each node in the list of nodes the heuristic value calculated by the number of
    # vertical nodes that are blocking the mouse (the third row) on its way to the exit.
    def H1(nodes):
        grid_width =  MouseInMaze.width
        for node_to_add in nodes:
            node_state = node_to_add.state
            mouse_location = node_state.find('*')
            i = mouse_location
            heuristic = 0
            while i < 3 * grid_width:
                if(node_state[i] >= 'a' and node_state[i] <= 'z'):
                    heuristic += 1
                i += 1
            node_to_add.heuristic = heuristic
    
    # Assign to each node in the list of nodes the heuristic value calculated by the sum of two numbers:
    # 1) the count of all connected vertical blocks such that one of the vertical blocks in each connected
    # component prevents the mouse from reaching the exit on the 3rd row.
    # 2) the count of distinct horizontal blocks that are connected to any of the groups of vertical blocks.
    # This sum is calculated once for the upper rows and once for the lower rows in each column location.
    # The minimum is added to the heuristic value.
    def H2(nodes):
        # expression evaluates to whether the block is horizontal
        expression = '((j % grid_width) > 0 and node_state[j - 1] == node_state[j])\
or ((j % grid_width) < grid_width - 1 and node_state[j + 1] == node_state[j])'
        grid_width =  MouseInMaze.width; grid_height = MouseInMaze.height
        for node_to_add in nodes:
            node_state = node_to_add.state
            mouse_location = node_state.find('*')
            i = mouse_location
            heuristic = 0
            # loop on all columns between the mouse and the exit on the 3rd row
            while i <= 3 * grid_width - 1:
                if(node_state[i] >= 'a' and node_state[i] <= 'z'):
                    end_search = 0
                    below_blocks = 1
                    above_blocks = 1
                    j = i + grid_width
                    # scan the lower side of the 3rd row
                    while j < grid_height * grid_width and not end_search:
                        if(node_state[j] != node_state[j-grid_width]):
                            if(node_state[j]=='.'):
                                break
                            elif eval(expression):
                                below_blocks += 1
                                end_search = 1
                                break
                            else:
                                below_blocks += 1
                        j += grid_width
                    if(not end_search):
                        j = i - grid_width
                        # scan the upper side of the 3rd row
                        while j >= 0:
                            if(node_state[j] != node_state[j+grid_width]):
                                if(node_state[j]=='.'):
                                    break
                                elif eval(expression):
                                    above_blocks += 1
                                    end_search = 1
                                    break
                                else:
                                    above_blocks += 1
                            j -= grid_width
                    heuristic += min(below_blocks, above_blocks)
                    if(end_search):
                        break
                i += 1
            node_to_add.heuristic = heuristic
            
    def G1(fringe, nodes):
        SearchAlgorithm.H1(nodes)
        fringe = fringe + nodes
        fringe = sorted(fringe, key=SearchAlgorithm.compare_greedy)
        return fringe
        
    def G2(fringe, nodes):
        SearchAlgorithm.H2(nodes)
        fringe = fringe + nodes
        fringe = sorted(fringe, key=SearchAlgorithm.compare_greedy)
        return fringe
        
    def A1(fringe, nodes):
        SearchAlgorithm.H1(nodes)
        fringe = fringe + nodes
        fringe = sorted(fringe, key=SearchAlgorithm.compare_a)
        return fringe
        
    def A2(fringe, nodes):
        SearchAlgorithm.H2(nodes)
        fringe = fringe + nodes
        fringe = sorted(fringe, key=SearchAlgorithm.compare_a)
        return fringe
        
    def search(problem, QingFn):
        expanded = 0 # number of nodes expanded
        SearchAlgorithm.visited = set() # a set of visited states, contains the string representation of the states
        nodes = SearchAlgorithm.make_queue(SearchAlgorithm.make_node(problem.initial_state))
        while nodes:
            node = nodes.pop(0)
            if node.state in SearchAlgorithm.visited:
                continue
            else:
                SearchAlgorithm.visited.add(node.state)
            if problem.goal_test(node.state):
                return node, expanded
            expanded += 1
            nodes = QingFn(nodes, problem.expand(node))
        return SearchAlgorithm.FAILURE, None
    
    def iterative_deepening(problem):
        i = 0
        expanded = 0
        while 1:
            result = SearchAlgorithm.depth_limited_search(problem, i)
            for x in SearchAlgorithm.visited:
                expanded += len(x)
            i += 1
            if result != SearchAlgorithm.CUT_OFF:
                return result, expanded - 1
    
    def depth_limited_search(problem, limit):
        SearchAlgorithm.visited = []
        for i in range(limit + 1):
            SearchAlgorithm.visited.append(set())
        return SearchAlgorithm.rec_dls(SearchAlgorithm.make_node(problem.initial_state), problem, limit)
    
    def rec_dls(node, problem, limit):
        cutoff = False
        if node.state in SearchAlgorithm.visited[node.depth]:
            return SearchAlgorithm.FAILURE
        SearchAlgorithm.visited[node.depth].add(node.state)
        if problem.goal_test(node.state):
            return node
        elif node.depth == limit:
            return SearchAlgorithm.CUT_OFF
        else:
            next_nodes = problem.expand(node)
            for successor in next_nodes:
                result = SearchAlgorithm.rec_dls(successor, problem, limit)
                if result == SearchAlgorithm.CUT_OFF:
                    cutoff = True
                elif result != SearchAlgorithm.FAILURE:
                    return result
        if cutoff:
            return SearchAlgorithm.CUT_OFF
        else:
            return SearchAlgorithm.FAILURE

    
def MiM(strategy, visualize, num):
    # create mousemaze instance
    confnum = num
    confstr = get_configuration(confnum)
    if confstr:
        problem = MouseInMaze(confstr)
    else:
        return
    import time
    start_time = time.process_time()
    # call search(problem, strategy)
    if strategy == SearchAlgorithm.iterative_deepening:
        result, expanded = SearchAlgorithm.iterative_deepening(problem)
    else:
        result, expanded = SearchAlgorithm.search(problem, strategy)
    end_time = time.process_time()
    if not result:
        print('No solution was found')
        return None, None, None
    else:
        print('A solution was found in ', result.depth, ' steps with ', expanded, ' nodes expanded in %.1f msec.' % ((end_time - start_time) * 1000))
        # if visualize create path
        if visualize:
            SearchAlgorithm.print_solution(result)
        return SearchAlgorithm.get_moves(result), result.cost, expanded

def get_configuration(config=1):
    f = open('Levels\Level' + str(config) + '.txt')
    config_str = ''
    for line in f:
        config_str += line[:-1]
    if len(config_str) == 36:
        return config_str
        
        
for i in range(1,11):
    print('Level '+str(i))
    print ('BFS')
    MiM(SearchAlgorithm.BFS, 0, i)
    print('DFS')
    MiM(SearchAlgorithm.DFS, 0, i)
    print('G1')
    MiM(SearchAlgorithm.G1, 0, i)
    print('G2')
    MiM(SearchAlgorithm.G2, 0, i)
    print('A1')
    MiM(SearchAlgorithm.A1, 0, i)
    print('A2')
    MiM(SearchAlgorithm.A2, 0, i)
    print('iterative deepening')
    MiM(SearchAlgorithm.iterative_deepening, 0, i)
    print('\n')